package algorithms.leaning.class25;

import common.util.MyUtil;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个只包含正数的数组arr，arr中任何一个子数组sub，
 * 一定都可以算出(sub累加和)* (sub中的最小值)是什么，
 * 那么所有子数组中，这个值最大是多少？
 *
 * @author guichang
 * @date 2021/6/27
 */

@SuppressWarnings("all")
public class Code2_单调栈_子数组最大指标 {

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            int[] nums = MyUtil.createRandomArray(10, 1, 20);
            MyUtil.print(maximumIndexOfSubArray(nums));
        }
    }

    /**
     * nums[i]做最小值时候的最大指标
     */
    public static int maximumIndexOfSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int N = nums.length;
        // 提前生成累加和数组
        int[] sums = new int[N + 1];
        for (int i = 0; i < N; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
        // 答案
        int res = 0;
        // 栈从上到下严格从大到小
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            // 有违反则弹出栈顶元素计算答案，相等弹出老的，新的进去，最大值按新的计算并不会漏掉
            while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
                int top = stack.pop(); // 当前位置可以计算了
                int left = stack.isEmpty() ? 0 : stack.peek() + 1; // 最左边能到的位置
                int right = i - 1; // 最右边能到的位置
                int target = nums[top] * betweenSum(sums, left, right); // 当前指标
                res = Math.max(res, target);
            }
            stack.push(i);
        }
        // 栈中还有数据，依次弹出做计算
        while (!stack.isEmpty()) {
            int top = stack.pop(); // 当前位置可以计算了
            int left = stack.isEmpty() ? 0 : stack.peek() + 1; // 最左边能到的位置
            int right = N - 1; // 最右边能到的位置
            int target = nums[top] * betweenSum(sums, left, right); // 当前指标
            res = Math.max(res, target);
        }
        return res;
    }

    /**
     * 获取i~j的累加和
     * 原数组     [1,2,3]
     * 累加和数组 [0,1,3,6]
     *
     * @param nums 累加和数组，原数组长度+1，首位为0
     */
    private static int betweenSum(int[] nums, int i, int j) {
        return nums[j + 1] - nums[i];
    }

}